package LimitedTimeGame.Day_0202;

/**
 * @author zxc
 * @date 2023/02/02 15:22
 **/
/**
 * 题目 ：和大于等于target的最短子数组
 * 题目详述 ：
 * 给定一个含有n个正整数的数组和一个正整数 target 。
 * 找出该数组中满足其和 ≥ target 的长度最小的 连续子数组[numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。
 * 如果不存在符合条件的子数组，返回 0 。
 *
 * 提示：
 * 1 <= target <= 109
 * 1 <= nums.length <= 105
 * 1 <= nums[i] <= 105
 *
 */
public class MinSubArrayLen02 {
    /**
     * 思路 ：
     * 滑动窗口,来实现子数组的获取;
     * @param target
     * @param nums
     * @return
     */
    public static void main(String[] args) {
        System.out.println(minSubArrayLen(7, new int[]{2,3,1,2,4,3}));
    }
    public static int minSubArrayLen(int target, int[] nums) {
        int len = nums.length;
        // 左指针 ：指向子数组的最左元素;
        int p1 = 0;
        // 右指针 ： 指向子数组的最右元素;
        int p2 = 0;
        int sum = 0;
        int minLnegth = len + 1;
        // 左指针p1 <= 右指针p2 && （右指针遍历所有元素之后，若是sum >= target，则左移左指针来寻找最短子数组）
        while(p2 <= len){
            if(sum < target){
                // 只有满足 右指针遍历完所有元素 && sum < target的条件，
                // ===》 遍历完所有可能的子数组;
                if(p2 == len){
                    break;
                }
                sum += nums[p2];
                p2++;
            }
            else {
                minLnegth = Math.min(minLnegth , p2 - p1);
                sum -= nums[p1];
                p1++;
            }
        }
        return minLnegth == len + 1 ? 0 : minLnegth;
    }
}
